package com.jame.basics.tree;

/**
 * @author : Jame
 * @date : 2021-01-19 16:48
 **/
public class RBTree<K extends Comparable<K>, V> {

    private static RBNode root;
    private static Boolean black = false;
    private static Boolean red = true;


    /**
     * 添加操作
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        if(key==null||value==null)
            new RuntimeException("Key Can't be empty Or Value Can't be empty");
        RBNode<K,V> t = this.root;
        if (t == null) {
            this.root = new RBNode<>(key, value);
            return null;
        }
        int cmp;
        //设置一个指针来指向父节点
        RBNode<K,V> parent;
        do {
            parent=t;
            cmp = key.compareTo((K) t.key);
            if(cmp>0){
                t=t.right;
            }else if(cmp<0){
                t=t.left;
            }else {
                V oldValue= (V) t.getValue();
                t.setValue(value);
                return  oldValue;
            }
        } while (t!=null);
        RBNode<K, V> node = new RBNode<>(key, value, parent);
        if(cmp<0){
            parent.left=node;
        }else{
            parent.right=node;
        }


        return null;
    }
    /*        f                    f
     *       /                    /
     *      p                    pr(r)
     *     / \                  / \
     *   pl   pr(r)   ==>      p   rr
     *       / \              / \
     *      rl  rr           pl  rl
     */

    /**
     * 左旋操作
     *
     * @param p
     */
    private void leftRotate(RBNode<K,V> p) {
        if (p != null) {
            RBNode<K,V> r = p.right;
            if (r != null) {
                p.right = r.left;
                r.left.father = p;

                if (p.father == null) {
                    root = r;
                } else if (p.father.left == p) {
                    p.father.left = r;
                    r.father = p.father;
                } else {
                    p.father.right = r;
                    r.father = p.father;
                }

                p.father = r;
                r.left = p;
            }
        }
    }

    /*            f                    f
     *           /                    /
     *          p                    pl(l)
     *         / \                  / \
     *    pl(l)   pr      ==>     ll   p
     *      / \                       / \
     *    ll   lr                   lr   pr
     */

    /**
     * 右旋操作
     *
     * @param p
     */
    private void rightRotate(RBNode<K,V> p) {
        if (p != null) {
            RBNode<K,V> l = p.left;
            if (l != null) {
                p.left = l.right;
                l.right.father = p;

                if (p.father == null) {
                    root = l;
                } else if (p.father.left == p) {
                    p.father.left = l;
                    l.father = p.father;
                } else {
                    p.father.right = l;
                    l.father = p.father;
                }
                p.father = l;
                l.right = p;
            }
        }
    }

    /**
     * RBNode 节点
     *
     * @param <K>
     * @param <V>
     */
    static class RBNode<K extends Comparable<K>, V> {
        private RBNode<K,V> father;
        private RBNode<K,V> left;
        private RBNode<K,V> right;
        //是否为红色
        private Boolean colour;
        private K key;
        private V value;

        public RBNode() {
        }

        public RBNode(K key, V value) {
            this.colour = black;
            this.key = key;
            this.value = value;
        }
        public RBNode(K key, V value,RBNode father) {
            this.father = father;
            this.colour = black;
            this.key = key;
            this.value = value;
        }

        public RBNode(RBNode<K,V> father, RBNode<K,V> left, RBNode<K,V> right, Boolean colour, K key, V value) {
            this.father = father;
            this.left = left;
            this.right = right;
            this.colour = colour;
            this.key = key;
            this.value = value;
        }

        public RBNode<K,V> getFather() {
            return father;
        }

        public void setFather(RBNode<K,V> father) {
            this.father = father;
        }

        public RBNode<K,V> getLeft() {
            return left;
        }

        public void setLeft(RBNode<K,V> left) {
            this.left = left;
        }

        public RBNode<K,V> getRight() {
            return right;
        }

        public void setRight(RBNode<K,V> right) {
            this.right = right;
        }

        public Boolean getColour() {
            return colour;
        }

        public void setColour(Boolean colour) {
            this.colour = colour;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }


}
